package com.peng.leetcode.tree;

import java.util.HashMap;
import java.util.Map;

/**
 * BuildTreeInorderAndPostorder
 * 106. 从中序与后序遍历序列构造二叉树
 * https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
 * <p>
 * Created on 2022/12/2
 *
 * @author lupeng
 */
public class BuildTreeInorderAndPostorder {

    public static void main(String[] args) {
//        [9,3,15,20,7]
//[9,15,7,20,3]

        TreeNode treeNode = new BuildTreeInorderAndPostorder().buildTree(new int[]{9, 3, 15, 20, 7}, new int[]{9, 15, 7, 20, 3});
        System.out.println(treeNode);
    }

    int[] postorder;
    Map<Integer, Integer> inorderVal2IndexMap = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            inorderVal2IndexMap.put(inorder[i], i);
        }
        this.postorder = postorder;
        return build(0, inorder.length - 1, 0, postorder.length - 1);
    }

    TreeNode build(int inorderLeft, int inorderRight, int postorderLeft, int postorderRight) {
        if (inorderLeft > inorderRight || postorderLeft > postorderRight) {
            return null;
        }
        int rootVal = postorder[postorderRight];
        Integer inorderRootIndex = inorderVal2IndexMap.get(rootVal);
        int subRightTreeLength = inorderRight - inorderRootIndex;
        TreeNode r = new TreeNode(rootVal);
        r.left = build(inorderLeft, inorderRootIndex - 1,
                postorderLeft, postorderRight - subRightTreeLength - 1);
        r.right = build(inorderRootIndex + 1, inorderRight,
                postorderRight - subRightTreeLength, postorderRight - 1);
        return r;
    }
}
